The present invention relates to computer graphics, and more particularly to displacement mapping.
Highly detailed surface models are becoming commonplace in the area of computer graphics, in part due to three-dimensional scanning technologies. Typically, these models are represented as dense triangle meshes. However, the irregularity and huge size of such meshes present challenges in manipulation, animation, rendering, transmission, and storage. FIG. 1 illustrates a surface 100 represented as dense triangle meshes.
Such surface 100 is an expensive representation because it stores:
(1) the irregular connectivity of faces,
(2) the (x,y,z) coordinates of the vertices,
(3) possibly several sets of texture parameterization coordinates (u,v) at the vertices, and
(4) texture images referenced by these parameterizations, such as color images and bump maps.
Examples of alternative representations will now be set forth that allow one to express a detailed surface as a displacement from a simpler, smooth domain surface.
A simple example of a displaced surface is terrain data expressed as a height field over a plane. The case of functions over the sphere has been considered in the past. See: Schrxc3x6der, P., and Sweldens, W. Spherical wavelets: efficiently representing functions on the sphere. Proceedings of SIGGRAPH 95, Computer Graphics, Annual Conference Series, pp. 161-172. Another example is a three-dimensional scan of a human head expressed as a radial function over a cylinder. However, even for this simple case of a head, artifacts are usually detectable at the ear lobes, where the surface is not a single-valued function over the cylindrical domain.
It has been shown that a detailed model can be represented as a displacement map over a network of B-spline patches. See: Krishnamurthy, V., and Levoy, M. Fitting smooth surfaces to dense polygon meshes. Proceedings of SIGGRAPH 96, Computer Graphics, Annual Conference Series, pp. 313-324. However, such B-spline patches resort to a vector-valued displacement map because the detailed model is not always an offset of their B-spline surface. Also, avoiding surface artifacts during animation requires that the domain surface be tangent-plane (C1) continuous, which involves constraints on the B-spline control points.
Many techniques have been developed in the past for modeling purposes. Such techniques involve subdivision surfaces, displacement maps, bump maps, and multiresolution subdivision.
Subdivision schemes defining smooth surfaces have been introduced in much documentation. By way of example, reference may be made to:
1) Catmull, E., and Clark, J. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design 10, pp. 350-355 (1978);
2) Doo, D., and Sabin, M. Behavior of recursive division surfaces near extraordinary points. Computer Aided Design 10, pp. 356-360 (1978); and
3) Loop, C. Smooth subdivision surfaces based on triangles. Master""s thesis, University of Utah, Department of Mathematics, 1987.
More recently, these schemes have been extended to allow surfaces with sharp features and fractionally sharp features. See:
1) DeRose, T., Kass, M., and Truong, T. Subdivision surfaces in character animation. Proceedings of SIGGRAPH 98, Computer Graphics, Annual Conference Series, pp. 85-94; and
2) Hoppe, H., DeRose, T., Duchamp, T., Halstead, M., Jin, H., McDonald, J., Schweitzer, J., and Stuetzle, W. Piecewise smooth surface reconstruction. Proceedings of SIGGRAPH 94, Computer Graphics, Annual Conference Series, pp. 295-302.
DeRose et al. define scalar fields over subdivision surfaces using subdivision masks. Hoppe et al. describe a method for approximating an original mesh with a much simpler subdivision surface. Such method does not, however, consider whether the approximation residual is expressible as a scalar displacement map.
The idea of displacing a surface by a function is set forth in Cook, R. Shade trees. Computer Graphics (Proceedings of SIGGRAPH 84), 18(3), pp. 223-231. Displacement maps have become popular commercially as procedural displacement shaders. The simplest displacement shaders interpolate values within an image, perhaps using standard bicubic filters. Though displacements may be in an arbitrary direction, they are almost always along the surface normal. See: Apodaca, A. and Gritz, L. Advanced RenderManxe2x80x94Creating CGI for Motion Pictures, Morgan Kaufmann, San Francisco, Calif., 1999.
Typically, normals on the displaced surface are computed numerically using a dense tessellation. While simple, this approach requires adjacency information that may be unavailable or impractical with low-level APIs and in memory-constrained environments (e.g. game consoles). Strictly local evaluation requires that normals be computed from a continuous analytic surface representation. However, it is difficult to piece together multiple displacement maps while maintaining smoothness. One encounters the same vertex enclosure problem as in the stitching of B-spline surfaces. While there are well-documented solutions to this problem, they require constructions with many more coefficients (9xc3x97in the best case), and may involve solving a global system of equations. For more information on the vertex enclosure problem set forth hereinabove, reference may be made to: Peters, J. Local smooth surface interpolation: a classification. Computer Aided Geometric Design, 7(1990), pp. 191-195.
A scheme has also been developed for approximating an arbitrary mesh using a B-spline patch network together with a vector-valued displacement map. In such scheme, the patch network is constructed manually by drawing patch boundaries on the mesh. Additional work has been done on surface pasting using the idea of adding a vector-valued displacement map to a spline surface. For more information on such concepts, reference may be made to:
1) Chan, K., Mann, S., and Bartels, R. World space surface pasting. Graphics Interface ""97, pp. 146-154;
2) Krishnamurthy, V., and Levoy, M. Fitting smooth surfaces to dense polygon meshes. Proceedings of SIGGRAPH 96, Computer Graphics, Annual Conference Series, pp. 313-324; and
3) Mann, S. and Yeung, T. Cylindrical surface pasting. Technical Report, Computer Science Dept., University of Waterloo (June 1999).
Hardware architecture has also been developed for rendering scalar-valued displacement maps over planar triangles. To avoid cracks between adjacent triangles of a mesh, the vertex normals may be interpolated across the triangle face, and the interpolated normal may be used to displace the surface. Such scheme permits adaptive tessellation in screen space. The importance of proper filtering when constructing mipmap levels in a displacement map should be recognized. The domain surface associated with the present technique is not smooth since it is a polyhedron. As such, animating a displaced surface using a polyhedral domain surface results in many surface artifacts. For more information on such hardware architecture, reference may be made to: Gumhold, S., and Hxc3xcttner, T. Multiresolution rendering with displacement mapping. SIGGRAPH workshop on Graphics hardware, Aug. 8-9, 1999.
An additional similar framework has been developed to express the geometry of one mesh as a displacement from another mesh, for the purpose of multiresolution shape deformation. For more information regarding such framework, reference may be made to: Kobbelt, L., Bareuther, T., and Seidel, H. P. Multi-resolution shape deformations for meshes with dynamic vertex connectivity. Proceedings of EUROGRAPHICS 2000.
With respect to displacement maps, there is a need for subdivision-based displacements that are inherently smooth. There is a further need for a surface representation that is more compact such that displaced surface normals may be computed more efficiently. Moreover, there is a need for unifying the representation around subdivision in order to simplify implementation and make operations such as magnification more natural.
Bump maps have been introduced and developed in much documentation. For example, reference may be made to:
1) Blinn, J. F. Simulation of wrinkled surfaces. Proceedings of SIGGRAPH 78, Computer Graphics, pp. 286-292;
2) Cohen, J., Olano, M. and Manocha, D. Appearance preserving Simplification. Proceedings of SIGGRAPH 98, Computer Graphics, Annual Conference Series, pp. 115-122;
3) Peercy, M., Airey, J. and Cabral, B. Efficient bump mapping hardware. Proceedings of SIGGRAPH 97, Computer Graphics, Annual Conference Series, pp. 303-306;
4) Cabral, B., Max, N. and Springmeyer, R. Bidirectional reflection functions from surface bump maps. Proceedings of SIGGRAPH 87, Computer Graphics, Annual Conference Series, pp.273-281; and
5) Apodaca, A. and Gritz, L. Advanced RenderManxe2x80x94Creating CGI for Motion Pictures, Morgan Kaufmann, San Francisco, Calif., 1999.
Blinn introduces the idea of perturbing the surface normal using a bump map. Peercy et al. present recent work on efficient hardware implementation of bump maps. Cohen et al. drastically simplify meshes by capturing detail in the related normal maps. Both Cabral et al. and Apodaca and Gritz discuss the close relationship of bump mapping and displacement mapping. Such documentation advocates combining them into a unified representation and resorting to true displacement mapping only when necessary.
Much documentation has been dedicated to the topic of multiresolution subdivision. For example, reference may be made to:
1) Lounsbery, M., DeRose, T., and Warren, J. Multiresolution analysis for surfaces of arbitrary topological type. ACM Transactions on Graphics, 16(1), pp. 34-73 (January 1997);
2) Zorin, D., Schrxc3x6der, P., and Sweldens, W. Interactive multiresolution mesh editing. Proceedings of SIGGRAPH 97, Computer Graphics, Annual Conference Series, pp. 259-268;
3) Eck, M., DeRose, Tr., Duchamp, T., loppe, H., Lounsbery, M., and Stuetzle, W. Multiresolution analysis of arbitrary meshes. Proceedings of SIGGRAPH 95, Computer Graphics, Annual Conference Series, pp. 173-182;
4) Lee, A., Sweldens, W., Schrxc3x6der, P., Cowsar, L., and Dobkin, D. MAPS: Multiresolution adaptive parameterization of surfaces. Proceedings of SIGGRAPH 98, Computer Graphics, Annual Conference Scries, pp. 95-104; and
5) Guskov, I., Vidimce, K., Sweldens, W., and Schrxc3x6der, P. Normal meshes. Proceedings of SIGGRAPH 2000, Computer Graphics, Annual Conference Series.
Lounsbery et al. apply multiresolution analysis to arbitrary surfaces. Given a parameterization of the surface over a triangular domain, they compress this (vector-valued) parameterization using a wavelet basis, where the basis functions are defined using subdivision of the triangular domain. Zorin et al. use a similar subdivision framework for multiresolution mesh editing. To make this multiresolution framework practical, several techniques have been developed for constructing a parameterization of an arbitrary surface over a triangular base domain. Eck et al. use Voronoi/Delaunay diagrams and harmonic maps, while Lee et al. track successive mappings during mesh simplification.
Guskov et al. represent a surface by successively applying a hierarchy of displacements to a mesh as it is subdivided. Their construction allows most of the vertices to be encoded using scalar displacements, but a small fraction of the vertices require vector displacements to prevent surface folding.
Regarding multiresolution subdivision, there is a need for a technique that does not support an arbitrary parameterization of the surface, and thus need only compress a scalar-valued function instead of vector-valued parameterization. In other words, there is a need for a process that only requires the storage of geometric detail, not parameterization data.
A representation is provided for displacement mapping. Included are a coarse first mesh, and a fine second mesh with a topology substantially similar to a topology of the first mesh. The second mesh includes a plurality of scalar values which each represent an offset between various points on the first mesh and the second mesh.